package graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @Description 图
 * @Time 2020-11-05 00:16
 * @Email 44867924@qq.com
 * @Auth fan
 * @Version 1.0v
 */
public class Graph {

    private ArrayList<String> vertexList;//存储顶点集合
    private int[][] edges;// 存储图对应的邻结矩阵
    private int numOfEdges;// 表示边的数目
    private boolean[] isVisited;// 标记是否被访问过了

    public static void main(String[] args) {
        // 测试
        int n = 5;// 结点的个数
        String[] vertexs = {"A", "B", "C", "D", "E"};
        Graph graph = new Graph(n);
        // 添加结点
        for (String vertex : vertexs) {
            graph.insertVertex(vertex);
        }
        // 添加边
        // AB AC BC BD BE
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);

        graph.showGrap();
        // 测试一把
        System.out.println("深度优先.......");
        graph.dfs();
        System.out.println();
        System.out.println("广度优先.......");
        graph.bfs();

    }

    public Graph(int n) {
        // 初始化矩阵和verTextList
        vertexList = new ArrayList<String>(n);
        edges = new int[n][n];
        numOfEdges = 0;
        // isVisited，放到这里，只能进行一种遍历，
       // isVisited = new boolean[n];
    }

    // 添加顶点
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 添加边
     *
     * @param v1     表示点的下标，即第几个点，如：A -> 0,B->1
     * @param v2     表示第二个顶点的下标
     * @param weight 表示权重，能走通为1，不有走就为0
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        // 边的数量加1；
        numOfEdges++;
    }

    /**
     * 得到当前结点的第一个邻接结点的下标 w
     *
     * @param index 表示当前结点的下载
     * @return 有就返回第一个邻接结点的下标，没有找到返回-1
     */
    public int getFirstNeighbor(int index) {
        for (int j = 0; j < vertexList.size(); j++) {
            // edges[index] 这个表示当前是哪个接点
            if (edges[index][j] > 0) {
                //edges[index][j] >0 判断是否可以到达下一下接点
                return j;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻接结点下标来获取下一个邻接结点的
     *
     * @param v1 当前结点，
     * @param v2 第一个邻接结点
     * @return
     */
    public int getNextNeighbor(int v1, int v2) {
        for (int j = v2 + 1; j < vertexList.size(); j++) {
            if (edges[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }


    /**
     * 深度优先遍历算法步骤
     * 1：访问初始结点v,并标记该结点已经被访问，也就是isVisited 对应的下标变为true
     * 2:查找结点v的第一个邻接结点 w
     * 3:若w存在，则继续4，如果w不存在，则回溯到第一步，将从v的下一个结点继续
     * 4：若w未被访问，对w进行深度优先遍历递归，（即把w当作另一个v,然后进行123）
     * 5：查找结点v的w邻接结点的下一个邻接结点，转到步骤3
     */

    /**
     * 深度优先算法
     *
     * @param isVisited
     * @param i         第一次就是0，1，2，3、、、、
     */
    public void dfs(boolean[] isVisited, int i) {
        // 首先我们访问该结点，输出
        System.out.print(getVertes(i) + "->");
        // 将该结点设置为已访问
        isVisited[i] = true;
        // 查找该结点的下一个结点w
        int w = getFirstNeighbor(i);
        while (w != -1) {// 说明有一下邻接结点
            if(!isVisited[w]){// 并且没有被访问过
                dfs(isVisited,w);
            }
            // 如果该结点被访问过了，就找当前结点的邻接结点的下一个接点
            w = getNextNeighbor(i,w);
        }
    }

    // 对dfs 进行一个重载,遍历我们所有的结点，并进行dfs
    public void dfs(){
        isVisited = new boolean[5];
        //历我们所有的结点，并进行dfs [回溯]
        for(int i = 0;i<getNumOfEdges();i++){
            if(!isVisited[i]){// 这个判断是为了提高效率
                dfs(isVisited,i);
            }
        }
    }

    /**
     * 广度优先遍历步骤
     * 1：访问初始结点v ，并标记为已访问
     * 2：结点v 加入队列（这个队列可以用likedlist来模拟，因为有，addlast removeFirst）
     * 3:当队列非空时，继续执行，否则当前点的广度优先遍历结束
     * 4：出队列，获取头结点u
     * 5:查找结点u 的第一个邻接结点w
     * 6:右结点u的邻接结点w 不存在，则转到步骤3，否则循环执行下面三个步骤
     * 6、1：若结点 w 未被访问过，则访问结点w并标记为已访问
     * 6、2：结点w入队列
     * 6、3：查找结点u的继w邻接结点的下一个结点邻接结点 w,转到步骤6
     */
    /**
     * 对一个结点进行广度优先遍历
     * @param isVisited
     * @param i
     */
    public void bfs(boolean[] isVisited,int i){
        int u;//表示队列的头结点对应的下标
        int w;//邻接结点w
        // 队列，记录访问结点的顺序
        LinkedList<Integer> queue = new LinkedList<>();
        //访问结点，并输入当前结点的值
        System.out.print(getVertes(i)+"=>");
        // 标记为已访问
        isVisited[i] = true;
        //将结点加入队列
        queue.addLast(i);

        while (!queue.isEmpty()){
            // 不为空，取出头结点
            u = queue.removeFirst();
            // 得到第一个邻接结点的下标w
            w = getFirstNeighbor(u);
            while(w != -1){// 找到了
                // 查看是否衩访问过
                if(!isVisited[w]){
                    //
                    System.out.print(getVertes(w)+"=>");
                    // 标记为已访问
                    isVisited[w] = true;
                    // 再入队
                    queue.addLast(w);

                }
                // 以u为前驱点，找w后面的下一个邻接点
                w = getNextNeighbor(u,w);
            }
        }
    }

    public void bfs(){
        isVisited = new boolean[5];
        //历我们所有的结点，并进行bfs [回溯]
        for(int i = 0;i<getNumOfEdges();i++){
            if(!isVisited[i]){// 这个判断是为了提高效率
                bfs(isVisited,i);
            }
        }
    }




    // 图中常用的方法

    /**
     * 返回结点的个数
     */
    public int getNumOfVertes() {
        return vertexList.size();
    }

    /**
     * 得到边的数目
     */
    public int getNumOfEdges() {
        return numOfEdges;
    }

    /**
     * 返回结点i(下标)对应的值，根我们添加的顺序有关
     *
     * @param i
     * @return
     */
    public String getVertes(int i) {
        return vertexList.get(i);
    }

    /**
     * 返回v1,v2之间的权值
     *
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    /**
     * 显示图对应的邻结矩阵
     */
    public void showGrap() {
        for (int[] link : edges) {
            System.out.println(Arrays.toString(link));
        }
    }


}
